#include <iostream>
#include <random>
#include <ctime>
#include <vector>
using namespace std;
ranlux48 engine(time(nullptr));//利用时间种子生成随机数引擎

//选定一个pivot并将left到right之间的元素通过pivot划分成两部分，然后返回pivot的下标
int _partition(vector<int> &nums, int left, int right) {
    //write ur code here.
    uniform_int_distribution<> distrib(left, right);//设置随机数范围，并为均匀分布
    int p = distrib(engine);//随机数
    swap(nums[p], nums[right]);
    int i = left, j = left; // [l,i)<nums[p]; [i,j]>=nums[p]
    while (j < right) {
        if (nums[j] < nums[right]) {
            swap(nums[i], nums[j]);
            i++;
        }
        j++;
    }
    swap(nums[i], nums[right]);
    return i;
}

//将nums通过_partition划分成两部分，对每个部分调用_quick_sort
void _quick_sort(vector<int> &nums, int left, int right) {
    //write ur code here.
    if (left >= right) return;
    bool is_sorted = true;
    for (size_t i = 1; is_sorted && i < nums.size();i++) {
        if (nums[i - 1] > nums[i]) is_sorted = false;
    }
    if (is_sorted) return;
    int p = _partition(nums, left, right);
    _quick_sort(nums, left, p - 1);
    _quick_sort(nums, p + 1, right);
}

void QuickSort(vector<int> &nums) {
    _quick_sort(nums, 0, nums.size() - 1);
}

#include "../tools.h"

int main(int argc, char const *argv[]) {
    /* code */
    vector<int> nums1{ 4,3,2,2,5 };
    vector<int> nums2{ 2,2,2,2,2 };
    QuickSort(nums1);
    QuickSort(nums2);
    print(nums1);
    print(nums2);
    return 0;
}

